package com.example.algorithm;

import java.util.LinkedList;
import java.util.Queue;

/**
 * 不同路径
 *
 * @author
 * @DATE 2024/6/30
 **/
public class LiKou62 {

    public static void main(String[] args) {
        System.out.println(uniquePaths2(3,7));
    }

    // 利用BFS实现
    public static int uniquePaths(int m, int n) {
        // 存储向右和向下两个方向
        int[][] directions = {{1, 0}, {0, 1}};
        Queue<int[]> queue = new LinkedList<>();
        // 将初始坐标加入队列
        queue.add(new int[]{0, 0});
        // 不同路径数量
        int count = 0;
        while (!queue.isEmpty()) {
            // 取出队首坐标
            int[] curr = queue.poll();
            // 坐标到达终点
            if (curr[0] == m - 1 && curr[1] == n - 1) {
                count++;
            } else {
                for (int[] direction : directions) {
                    // 遍历2个方向
                    int x = curr[0] + direction[0];
                    int y = curr[1] + direction[1];
                    if (x >= 0 && x < m && y >= 0 && y < n) {
                        // 坐标未越界，则将新坐标加入队列
                        queue.add(new int[]{x, y});
                    }
                }
            }
        }
        return count;
    }

    // 利用动态规划实现
    public static int uniquePaths2(int m, int n) {
        // 思路:由于在每个位置只能向下或者向右， 所以每个坐标的路径和等于上一行相同位置和上一列相同位置不同路径的总和，
        // 状态转移方程：f[i][j] = f[i - 1][j] + f[i][j - 1];
        int[][] dp = new int[m][n];
        for (int i = 0; i < m; i++) {
            // 第i行，第0列，路径都是1
            dp[i][0] = 1;
        }
        for (int i = 0; i < n; i++) {
            // 第0行，第i列，路径都是1
            dp[0][i] = 1;
        }
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
            }
        }
        return dp[m-1][n-1];
    }
}
